/*
*给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。
*请你返回所有和为 0 且不重复的三元组。
*注意：答案中不可以包含重复的三元组。
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> threeSum(vector<int>& nums) 
{
    vector <vector<int>> res;
    if(nums.size()<3)
        return res;   

    sort(nums.begin(),nums.end());
    
    if(nums[0]>0)
        return res;
    for(int i=0;i<nums.size()-2;i++)
    {
        if(nums[i]>0)
            break;
        if(i>0&&nums[i]==nums[i-1])
            continue;
        int left = i + 1;
        int right = nums.size() - 1;
        while(left<right)
        {
            if(nums[i] + nums[left] + nums[right]>0)
                right--;
            else if(nums[i] + nums[left] + nums[right]<0)
                left++;
            else
            {
                res.push_back({nums[i],nums[left],nums[right]});
                while(right>2&&nums[right]==nums[right-1]){right--;}
                while(left<nums.size()-3&&nums[left]==nums[left+1]){left++;}//需要注意数组的范围
                right--;
                left++;
            }
                

        }
    }
    return res;        
}


int main(void)
{
    vector<int> nums = {-1,0,1,2,-1,-4};
    vector<vector<int>> res = threeSum(nums);
    for(int i=0;i<res.size();i++)
    {
        for(int j=0;j<res[i].size();j++)
        {
            cout<<res[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}